package NowCoder.DynamicPlanning;
import java.util.*;
/**
 *
 * DD1 连续最大和
 * 简单  通过率：22.41%  时间限制：1秒  空间限制：32M
 * 知识点 动态规划 贪心
 * warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
 * 描述
 * 一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3
 * 输入描述：
 * 输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。
 * 输出描述：
 * 所有连续子数组中和最大的值。
 * 示例1
 * 输入：
 * 3
 * -1 2 1
 * 复制
 * 输出：
 * 3
 * https://www.nowcoder.com/practice/5a304c109a544aef9b583dce23f5f5db?tpId=182&tqId=34613&ru=/exam/oj
 */
public class 连续最大和_DD1 {
    //TODO:请重新写这一道题
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int sums=0, maxsums=Integer.MIN_VALUE; //考虑全为负数的情况
        for(int i= 0 ;i < n;i++){
            sums+=scanner.nextInt();
            maxsums=Math.max(maxsums,sums);
            sums= Math.max(sums, 0); //代码核心了，如果当前求和为负，则抛弃之前的连续数组，重新开始求和
        }
        System.out.println(maxsums);
    }
}
